//
// Description: 438. 找到字符串中所有字母异位词
// Created by Loading on 2022/7/30.
//

#include <bits/stdc++.h>

using namespace std;

vector<int> findAnagrams(string s, string p) {
    int n = s.size(), m = p.size();
    if (m > n) {
        return {};
    }
    vector<int> res;
    // diff 表示当前窗口中，与 p 串不同的字符数量
    int diff = 0;
    // 统计每个字符的相对数量
    vector<int> count(26);
    for (int i = 0; i < m; ++i) {
        ++count[s[i] - 'a'];
        --count[p[i] - 'a'];
    }
    for (int i = 0; i < 26; ++i) {
        if (count[i]) {
            ++diff;
        }
    }
    if (!diff) {
        res.emplace_back(0);
    }

    for (int i = 0; i < n - m; ++i) {
        int a = s[i] - 'a';
        // 窗口右移，去掉最左侧字符
        --count[a];
        if (count[a] == 0) { // 去掉后数量为 0，说明去掉之后此字符相同，自减diff
            --diff;
        } else if (count[a] == -1) { // 去掉后数量为 -1，说明去掉之前此字符相同，自增diff
            ++diff;
        }
        int b = s[i + m] - 'a';
        // 窗口右移，加入最右侧字符
        ++count[b];
        if (count[b] == 0) { // 加入后数量为 0，说明加入之后此字符相同，自减diff
            --diff;
        } else if (count[b] == 1) { // 加入后数量为 1，说明加入之前此字符相同，自增diff
            ++diff;
        }
        // 判断 diff 是否为 0
        if (!diff) {
            res.emplace_back(i + 1);
        }
    }

    return res;
}

int main() {
    string s = "cbaebabacd", p = "abc";
    auto res = findAnagrams(s, p);

    for (auto x : res) {
        cout << x << ' ';
    }

    return 0;
}